package com.chaos.eurekaproducer.leetCode.sort;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @author liaopeng
 * @title: QuickSort
 * @projectName eureka-producer
 * @description: 快速排序
 * @date 2021/7/7下午2:19
 */
public class QuickSort {
    public static void quickSort(int[] a,int p,int r){
        if (p>=r){
            return;
        }
        int pivot = getPivot(a, p, r);
        quickSort(a,0,pivot-1);
        quickSort(a,pivot+1,r);
    }

    /**
     * 将数组分为三个部分：分区点、小于分区点区间、大于分区点区间
     * 最后结果就是将元素放到对应的区间中,即小于分区点的在左边，大于分区点的在右边
     * 1、找一个数作为分区值，此处找最后一个元素
     * 2、定义两个游标i、j，i的位置就是分区点应该在的位置
     * 3、如果a[j]小于分区点则将a[j]插入到小于分区点的区间即a[i]的左边
     *   因为数组插入复杂度是O(n)，所以此处使用交换元素来实现插入
     * 4、遍历完了之后交换开始定义的分区点和a[i],即将分区点放到它应该在的位置
     * @param a
     * @param p
     * @param r
     * @return
     */
    public static int getPivot(int[] a,int p,int r){
        int i=p;
        int value=a[r];
        for (int j = p; j < r; j++) {
            if (a[j]<value){
                int temp = a[j];
                a[j]=a[i];
                a[i] = temp;
                i++;
            }
        }
        //交换，将分区点值放在其应该在的位置
        int temp = a[i];
        a[i] = value;
        a[r] = temp;
        return i;
    }


    public static void main(String[] args) {
        int[] a = new int[]{3,4,6,1,2};
        quickSort(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            int i1 = a[i];
            System.out.println(i1);
        }
    }
}
